package name.huzhenbo.java.algorithm.search;

/**
 * O(nlogn)
 */
class DuplicatePartSearcher {
    private String input;

    public DuplicatePartSearcher() {
    }

    public void setInput(String input) {
        this.input = input;
    }

    public String go() {
        // in c or c++, we can replace the indexes array by the pointers array, and access of the suffix will be more
        // efficient.
        int[] sortedSuffixIndexes = sort(initSuffixIndexes());

        int max = 0;
        String longestMatch = null;
        for (int i = 1; i < sortedSuffixIndexes.length; i++) {
            int count = equalsCharsCount(sortedSuffixIndexes[i - 1], sortedSuffixIndexes[i]);
            if (max < count) {
                max = count;
                longestMatch = suffix(sortedSuffixIndexes[i - 1]).substring(0, count);
            }
        }
        return longestMatch;
    }

    private int[] initSuffixIndexes() {
        int[] indexes = new int[input.length()];
        for(int i = 0; i < indexes.length; i++){
            indexes[i] = i;
        }
        return indexes;
    }

    private int equalsCharsCount(int index1, int index2) {
        char[] suffixChars1 = suffix(index1).toCharArray();
        char[] suffixChars2 = suffix(index2).toCharArray();

        int len = index1 > index2 ? suffixChars1.length : suffixChars2.length;
        int count = 0;
        for (int i = 0; i < len; i++) {
            if (suffixChars1[i] != suffixChars2[i]) break;
            count++;
        }
        return count;
    }

    private int[] sort(int[] indexes) {
        _sort(indexes, 0, indexes.length - 1);
        return indexes;
    }

    private void _sort(int[] indexes, int start, int end) {
        if (start >= end) {
            return;
        }
        String base = suffix(indexes[start]);
        int i = start + 1;
        int j = end;
        while (true) {
            while (i <= end && suffix(indexes[i]).compareTo(base) <= 0) {
                i++;
            }
            while (j >= start + 1 && suffix(indexes[j]).compareTo(base) >= 0) {
                j--;
            }
            if (j <= i) {
                break;
            }
            swap(indexes, i, j);
        }
        swap(indexes, start, j);
        _sort(indexes, start, j - 1);
        _sort(indexes, j + 1, end);
    }

    private String suffix(int index) {
        return input.substring(index);
    }

    private void swap(int[] indexes, int i, int j) {
        int temp = indexes[i];
        indexes[i] = indexes[j];
        indexes[j] = temp;
    }
}
